home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / pc / files / t_unix / j109lxa4.tar / lzw.c < prev    next >
C/C++ Source or Header  |  1994-06-04  |  15KB  |  584 lines
  1. /*        SM0RGV data compression routines.
  2.  * This file implements the Lempel-Ziv Welch (LZW) data compression
  3.  * algorithm but with a variable code size, as in GIF format files.
  4.  *
  5.  * Copyright 1990 by Anders Klemets, SM0RGV. Permission granted for
  6.  * non-commercial distribution only.
  7.  */
  8.  
  9. #include <ctype.h>
  10. #include "global.h"
  11. #include "config.h"
  12. #ifdef    LZW
  13. #include "mbuf.h"
  14. #include "proc.h"
  15. #include "lzw.h"
  16. #include "socket.h"
  17. #include "usock.h"
  18. #include "session.h"
  19. #include "cmdparse.h"
  20.  
  21. static void fastencode __ARGS((struct usock *up,char data));
  22. static void morebits __ARGS((struct lzw *lzw));
  23. static void cleartbl __ARGS((struct lzw *lzw));
  24. static void addtobuffer __ARGS((struct usock *up,int32 code));
  25. static void addchar __ARGS((char data,struct lzw *lzw));
  26. static void getstring __ARGS((int32 code,struct lzw *lzw));
  27. static char firstchar __ARGS((int32 code,struct lzw *lzw));
  28. static void decodetbl __ARGS((int32 code,struct lzw *lzw));
  29. static int32 nextcode __ARGS((struct usock *up));
  30.  
  31. int
  32. #ifdef PROTOTYPES
  33. dolzw(int argc,char **argv,void *p)
  34. #else
  35. dolzw(argc,argv,p)
  36. int argc;
  37. char *argv[];
  38. void *p;
  39. #endif
  40. {
  41.     if(argc > 1) {
  42.         switch(tolower(*argv[1])) {
  43.         case 'm':
  44.             if(argc == 2) {
  45.                 tprintf("LZW mode: %s\n",Lzwmode ? "fast" : "compact");
  46.             } else {
  47.                 Lzwmode = (tolower(*argv[2]) == 'f');
  48.             }
  49.             return 0;
  50.         case 'b':
  51.             argc--;
  52.             argv++;
  53.             return setintrc(&Lzwbits,"LZW bits",argc,argv,9,16);
  54.         case '=':
  55.             if(argc == 3) {
  56.                 struct session *sp;
  57.                 if((sp = sessptr(argv[2])) != NULLSESSION) {
  58.                     lzwinit(sp->s,Lzwbits,Lzwmode);
  59.                 }
  60.             }
  61.             return 0;
  62.         }
  63.     }
  64.     tputs("Usage: lzw <mode|bits>\n");
  65.     return -1;
  66. }
  67.  
  68. /* Initialize a socket for compression. Bits specifies the maximum number
  69.  * of bits per codeword. The input and output code tables might grow to
  70.  * about (2^bits * 3) bytes each. The bits parameter does only serve as a
  71.  * recommendation for the decoding, the actual number of bits may be
  72.  * larger, but not never more than 16.
  73.  */
  74. void
  75. lzwinit(s,bits,mode)
  76. int s;        /* socket to operate on */
  77. int bits;    /* maximum number of bits per codeword */
  78. int mode;    /* compression mode, LZWCOMPACT or LZWFAST */
  79. {
  80.     struct usock *up;
  81.     if((up = itop(s)) == NULLUSOCK)
  82.         return;
  83.     up->zout = (struct lzw *) callocw(1,sizeof(struct lzw));
  84.     up->zin = (struct lzw *) callocw(1,sizeof(struct lzw));
  85.     up->zout->codebits = LZWBITS;
  86.     if(bits < LZWBITS)
  87.         up->zout->maxbits = LZWBITS;
  88.     if(bits > 16 || bits == 0)
  89.         up->zout->maxbits = 16;
  90.     if(bits >= LZWBITS && bits <= 16)
  91.         up->zout->maxbits = bits;
  92.     up->zout->nextbit = 0;
  93.     up->zout->prefix = -1;
  94.     up->zout->version = -1;
  95.     up->zout->code = -1;
  96.     up->zout->mode = mode;
  97.     up->zout->next = ZFLUSH + 1;    /* used only in LZWFAST mode */
  98.     up->zin->codebits = LZWBITS;
  99.     up->zin->maxbits = -1;
  100.     up->zin->nextbit = 0;
  101.     up->zin->prefix = -1;
  102.     up->zin->version = -1;
  103.     up->zin->code = -1;
  104.     up->zin->next = ZFLUSH + 1;
  105.     up->zin->mode = LZWCOMPACT;
  106.     up->zin->buf = NULLBUF;
  107. }
  108.  
  109. void
  110. lzwfree(up)
  111. struct usock *up;
  112. {
  113.     if(up->zout != NULLLZW) {
  114.         cleartbl(up->zout);
  115.         free((char *)up->zout);
  116.         up->zout = NULLLZW;
  117.     }
  118.     if(up->zin != NULLLZW) {
  119.         cleartbl(up->zin);
  120.         free_q(&up->zin->buf);
  121.         free((char *)up->zin);
  122.         up->zin = NULLLZW;
  123.     }
  124. }
  125. /* LZW encoding routine.
  126.  * See if the string specified by code + data is in the string table. If so,
  127.  * set prefix equal to the code of that string. Otherwise insert code + data
  128.  * in the string and set prefix equal to data.
  129.  */
  130. void
  131. lzwencode(s,data)
  132. int s;
  133. char data;
  134. {
  135.     struct usock *up;
  136.     register struct lzw *lzw;
  137.     int32 code, pagelim;
  138.     register unsigned int i,j;
  139.  
  140.     if((up = itop(s)) == NULLUSOCK)
  141.         return;
  142.     lzw = up->zout;
  143.     code = up->zout->prefix;
  144.     /* the first byte sent will be the version number */
  145.     if(lzw->version == -1) {
  146.         lzw->version = ZVERSION;
  147.         up->obuf->data[up->obuf->cnt++] = lzw->version;
  148.         /* then send our recommended maximum number of codebits */
  149.         up->obuf->data[up->obuf->cnt++] = lzw->maxbits;
  150.     }
  151.     lzw->cnt++;
  152.     if(code == -1) {
  153.         lzw->prefix = (int32) uchar(data);
  154.         return;
  155.     }
  156.     if(lzw->mode == LZWFAST) {
  157.         fastencode(up,data);
  158.         return;
  159.     }
  160.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  161.     if(code <= ZFLUSH)
  162.         i = j = 0;
  163.     else {
  164.         i = (code - ZFLUSH) / LZWBLK;
  165.         j = (code - ZFLUSH) % LZWBLK;
  166.     }
  167.     if(lzw->tu.tbl == (struct zentry **)0)
  168.         lzw->tu.tbl = (struct zentry **) callocw(1,
  169.             sizeof(struct zentry *) * pagelim);
  170.     for(;;) {
  171.         if(itop(s) == NULLUSOCK) /* the connection has been closed */
  172.             return;
  173.         if(up->zout == NULLLZW) /* ...or is about to be closed */
  174.             return;
  175.         if(lzw->tu.tbl[i] == (struct zentry *)0) {
  176.             lzw->tu.tbl[i] = (struct zentry *)
  177.                 mallocw(LZWBLK * sizeof(struct zentry));
  178.             memset((char *)lzw->tu.tbl[i], 0xff,
  179.                 LZWBLK * sizeof(struct zentry));
  180.         }
  181.         while(j < LZWBLK) {
  182.             if(lzw->tu.tbl[i][j].data == data &&
  183.                 lzw->tu.tbl[i][j].code == (int16) code) {
  184.                 lzw->prefix = (int32)(i * LZWBLK + j +
  185.                               ZFLUSH + 1);
  186.                 return;
  187.             }
  188.             if(lzw->tu.tbl[i][j].code == 0xffff) {
  189.                 lzw->tu.tbl[i][j].code = (int16) code;
  190.                 lzw->tu.tbl[i][j].data = data;
  191.                 addtobuffer(up,code);
  192.                 lzw->prefix = (int32) uchar(data);
  193.                 lzw->next++;
  194.                 if(lzw->next ==    (int32) 1 << lzw->codebits)
  195.                     /* the current table is now full */
  196.                     morebits(lzw);
  197.                 if(lzw->next + 1 == (int32)
  198.                         1 << lzw->maxbits) {
  199.                 /* The last codeword has been reached.
  200.                  * (Or last - 1.) Signal this and start all
  201.                  * over again.
  202.                  */
  203.                     addtobuffer(up,lzw->prefix);
  204.                        if(lzw->next + 1 == (int32)
  205.                             1 << lzw->codebits)
  206.                         morebits(lzw);
  207.                     addtobuffer(up,ZCC);
  208.                     cleartbl(lzw);
  209.                 }
  210.                 return;
  211.             }
  212.             ++j;
  213.         }
  214.         pwait(NULL);
  215.         ++i;
  216.         j = 0;
  217.     }
  218. }
  219.  
  220. /* Used when LZWFAST mode is selected. Memory usage approx. (2^bits * 5)
  221.  * bytes.
  222.  */
  223. static void
  224. fastencode(up,data)
  225. struct usock *up;
  226. char data;
  227. {
  228.     register struct zfast *z;
  229.     register struct mbuf *bp;
  230.     register struct lzw *lzw = up->zout;
  231.     int32 code = up->zout->prefix;
  232.     register int16 cnt, h;
  233.  
  234.     if(lzw->tu.bpp == NULLBUFP)
  235.         lzw->tu.bpp = (struct mbuf **) callocw(1,
  236.             sizeof(struct mbuf *) * ZHASH);
  237.     h = lobyte(code);
  238.     h ^= hibyte(code);
  239.     h ^= data;
  240.     h = h % ZHASH;
  241.     if(lzw->tu.bpp[h] == NULLBUF)
  242.         lzw->tu.bpp[h] = ambufw(LZWBLK);
  243.     bp = lzw->tu.bpp[h];
  244.     cnt = bp->cnt / sizeof(struct zfast);
  245.     z = (struct zfast *) bp->data;
  246.     while(cnt > 0) {
  247.         if(z->data == data && z->code == (int16) code) {
  248.             lzw->prefix = (int32) z->owncode;
  249.             return;
  250.         }
  251.         z++;
  252.         if(--cnt == 0) {
  253.             if(bp->next == NULLBUF)
  254.                 break;
  255.             bp = bp->next;
  256.             cnt = bp->cnt / sizeof(struct zfast);
  257.             z = (struct zfast *) bp->data;
  258.         }
  259.     }
  260.     if(bp->size - bp->cnt >= sizeof(struct zfast)) {
  261.         z = (struct zfast *) &bp->data[bp->cnt];
  262.         bp->cnt += sizeof(struct zfast);
  263.     }
  264.     else {
  265.         bp->next = ambufw(LZWBLK);
  266.         z = (struct zfast *) bp->next->data;
  267.         bp->next->cnt = sizeof(struct zfast);
  268.     }
  269.     z->code = (int16) code;
  270.     z->data = data;
  271.     z->owncode = (int16) lzw->next++;
  272.     addtobuffer(up,code);
  273.     lzw->prefix = (int32) uchar(data);
  274.     if(lzw->next == (int32) 1 << lzw->codebits) {
  275.         /* Increase the number of bits per codeword */
  276.         morebits(lzw);
  277.     }
  278.     if(lzw->next + 1 == (int32) 1 << lzw->maxbits) {
  279.         /* The last codeword has been reached. (Or last - 1.)
  280.          * Signal this and start all over again.
  281.          */
  282.         addtobuffer(up,lzw->prefix);
  283.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  284.             morebits(lzw);
  285.         addtobuffer(up,ZCC);
  286.         cleartbl(lzw);
  287.     }
  288.     pwait(NULL);
  289. }
  290.  
  291. /* increase the number of significant bits in the codewords, and increase
  292.  * the size of the string table accordingly.
  293.  */
  294. static void
  295. morebits(lzw)
  296. struct lzw *lzw;
  297. {
  298.     struct zentry **newt;
  299.     int32 pagelim, oldp;
  300.     oldp = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  301.     lzw->codebits++;
  302.     if(lzw->mode == LZWFAST)
  303.         return;
  304.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  305.     newt = (struct zentry **) callocw(1,sizeof(struct zentry *)*pagelim);
  306.     memcpy(newt,lzw->tu.tbl,sizeof(struct zentry *) * oldp);
  307.     free((char *)lzw->tu.tbl);
  308.     lzw->tu.tbl = newt;
  309. }
  310.  
  311. static void
  312. cleartbl(lzw)
  313. struct lzw *lzw;
  314. {
  315.     int32 pagelim,i;
  316.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  317.     lzw->codebits = LZWBITS;
  318.     lzw->prefix = -1;
  319.     lzw->next = ZFLUSH + 1;
  320.     if(lzw->tu.p == NULL)
  321.         return;
  322.     if(lzw->mode == LZWCOMPACT)
  323.         for(i=0; i < pagelim; ++i)
  324.             free((char *)lzw->tu.tbl[i]);
  325.     else
  326.         for(i=0; i < ZHASH; ++i)
  327.             free_p(lzw->tu.bpp[i]);
  328.     free((char *)lzw->tu.p);
  329.     lzw->tu.p = NULL;
  330. }
  331. /* Add a codeword to the code stream. Nextbit indicates at which bit in the
  332.  * code stream should be written first. The codeword ZFLUSH is used to
  333.  * pad the buffer to a byte boundary when the buffer will be flushed.
  334.  * The remaining bits of the ZFLUSH codeword are sent in the next buffer.
  335.  */
  336. static void
  337. addtobuffer(up,code)
  338. struct usock *up;
  339. int32 code;
  340. {
  341.     if(up->zout->code != -1) {
  342.         /* Insert remaining bits of ZFLUSH codeword */
  343.         up->obuf->data[up->obuf->cnt] =
  344.              up->zout->code >> up->zout->flushbit;
  345.         if(up->zout->flushbit + 8 >= up->zout->codebits) { /* done */
  346.             up->zout->nextbit = (up->zout->codebits -
  347.                         up->zout->flushbit) % 8;
  348.             if(up->zout->nextbit == 0)
  349.                 ++up->obuf->cnt;
  350.             up->zout->code = -1;
  351.         }
  352.         else {
  353.             /* not done yet */
  354.             ++up->obuf->cnt;
  355.             up->zout->flushbit += 8;
  356.             addtobuffer(up,code);
  357.             return;
  358.         }
  359.     }
  360.     /* normal codewords are treated here */
  361.     if(up->zout->nextbit == 0) {
  362.         /* we are at a byte boundary */
  363.         if(code == ZFLUSH) {
  364.             up->zout->flushbit = 0;
  365.             up->zout->code = ZFLUSH;
  366.             return;
  367.         }
  368.         up->obuf->data[up->obuf->cnt++] = (char) code;
  369.     }
  370.     else
  371.         up->obuf->data[up->obuf->cnt++] |= code << up->zout->nextbit;
  372.     if(code == ZFLUSH) {
  373.         /* interrupt here and save the rest of the ZFLUSH
  374.          * codeword for later.
  375.          */
  376.         up->zout->flushbit = 8 - up->zout->nextbit;
  377.         up->zout->code = ZFLUSH;
  378.         return;
  379.     }
  380.     up->obuf->data[up->obuf->cnt] = code >> (8 - up->zout->nextbit);
  381.     /* start on a third byte if necessary */
  382.     if(16 - up->zout->nextbit < up->zout->codebits)
  383.         up->obuf->data[++up->obuf->cnt] =
  384.                     code >> (16 - up->zout->nextbit);
  385.     up->zout->nextbit = (up->zout->nextbit + up->zout->codebits) % 8;
  386.     if(up->zout->nextbit == 0)
  387.         ++up->obuf->cnt;
  388. }
  389.  
  390. void
  391. lzwflush(up)
  392. struct usock *up;
  393. {
  394.     /* interrupt the encoding process and send the prefix codeword */
  395.     if(up->zout->prefix != -1) {
  396.         addtobuffer(up,up->zout->prefix);
  397.            if(up->zout->next + 1 == (int32) 1 << up->zout->codebits)
  398.             morebits(up->zout);
  399.         up->zout->prefix = -1;
  400.     }
  401.     /* signal this by sending the ZFLUSH codeword */
  402.     addtobuffer(up,ZFLUSH);
  403. }
  404.  
  405. int
  406. lzwdecode(up)
  407. struct usock *up;
  408. {
  409.     int32 code,data;
  410.     if(up->zin->version == -1 && (up->zin->version = PULLCHAR(&up->ibuf))
  411.        == -1)
  412.         return -1;
  413.     if(up->zin->maxbits == -1) {
  414.         /* receive a recommended value for the maximum no of bits */
  415.         if((up->zin->maxbits = PULLCHAR(&up->ibuf)) == -1)
  416.             return -1;
  417.         if(up->zout->maxbits > up->zin->maxbits) {
  418.             if(up->zout->codebits > up->zin->maxbits) {
  419.                 /* We are already using more bits than our
  420.                  * peer want us to, so clear the encoding
  421.                  * table immediately.
  422.                  */
  423.                 addtobuffer(up,up->zout->prefix);
  424.                 if(up->zout->next + 1 == (int32)
  425.                    1 << up->zout->codebits)
  426.                     morebits(up->zout);
  427.                 addtobuffer(up,ZCC);
  428.                 cleartbl(up->zout);
  429.             }
  430.             up->zout->maxbits = up->zin->maxbits;
  431.         }
  432.     }
  433.     for(;;) {
  434.         if((data = PULLCHAR(&up->zin->buf)) != -1)
  435.             return (int) data;
  436.         if((code = nextcode(up)) == -1)
  437.             return -1;
  438.         decodetbl(code,up->zin);
  439.         up->zin->cnt += len_p(up->zin->buf);
  440.     }
  441. }
  442.  
  443. static void
  444. addchar(data,lzw)
  445. char data;
  446. struct lzw *lzw;
  447. {
  448.     lzw->buf = pushdown(lzw->buf,1);
  449.     *lzw->buf->data = data;
  450. }
  451. static void
  452. getstring(code,lzw)
  453. int32 code;
  454. struct lzw *lzw;
  455. {
  456.     int i,j;
  457.     for(;;) {
  458.         if(code < ZFLUSH) {
  459.             addchar(uchar(code),lzw);
  460.             return;
  461.         }
  462.         i = (code - ZFLUSH - 1) / LZWBLK;
  463.         j = (code - ZFLUSH - 1) % LZWBLK;
  464.         addchar(lzw->tu.tbl[i][j].data,lzw);
  465.         code = (int32) lzw->tu.tbl[i][j].code;
  466.     }
  467. }
  468. static char
  469. firstchar(code,lzw)
  470. int32 code;
  471. struct lzw *lzw;
  472. {
  473.     int i,j;
  474.     for(;;) {
  475.         if(code < ZFLUSH)
  476.             return uchar(code);
  477.         i = (code - ZFLUSH - 1) / LZWBLK;
  478.         j = (code - ZFLUSH - 1) % LZWBLK;
  479.         code = (int32) lzw->tu.tbl[i][j].code;
  480.     }
  481. }
  482. static void
  483. decodetbl(code,lzw)
  484. int32 code;
  485. struct lzw *lzw;
  486. {
  487.     register unsigned int i,j;
  488.     int32 pagelim;
  489.  
  490.     if(code > lzw->next) {
  491.         printf("LZW protocol error, process %s\n",Curproc->name);
  492.         return;
  493.     }
  494.     if(lzw->buf == NULLBUF) {
  495.         lzw->buf = ambufw(512);
  496.         /* allow us to use pushdown() later */
  497.         lzw->buf->data += lzw->buf->size;
  498.     }
  499.     if(lzw->prefix == -1) {
  500.         getstring(code,lzw);
  501.         lzw->prefix = code;
  502.         return;
  503.     }
  504.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  505.     if(lzw->tu.tbl == (struct zentry **)0)
  506.         lzw->tu.tbl = (struct zentry **) callocw(1,
  507.                 sizeof(struct zentry *) * pagelim);
  508.     if(code < ZFLUSH)
  509.         goto intable;
  510.     i = (code - ZFLUSH - 1) / LZWBLK;
  511.     j = (code - ZFLUSH - 1) % LZWBLK;
  512.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  513.         lzw->tu.tbl[i] = (struct zentry *)
  514.                 mallocw(LZWBLK * sizeof(struct zentry));
  515.         memset((char *)lzw->tu.tbl[i], 0xff,
  516.                 LZWBLK * sizeof(struct zentry));
  517.     }
  518.     if(lzw->tu.tbl[i][j].code == 0xffff) {
  519.         lzw->tu.tbl[i][j].data = firstchar(lzw->prefix,lzw);
  520.         lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  521.         getstring(code,lzw);
  522.         lzw->next = code + 1;
  523.         lzw->prefix = code;
  524.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  525.             morebits(lzw);
  526.         return;
  527.     }
  528. intable:
  529.     getstring(code,lzw);
  530.     i = (lzw->next - ZFLUSH - 1) / LZWBLK;
  531.     j = (lzw->next - ZFLUSH - 1) % LZWBLK;
  532.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  533.         lzw->tu.tbl[i] = (struct zentry *)
  534.                 mallocw(LZWBLK * sizeof(struct zentry));
  535.         memset((char *)lzw->tu.tbl[i], 0xff,
  536.                 LZWBLK * sizeof(struct zentry));
  537.     }
  538.     lzw->tu.tbl[i][j].data = firstchar(code,lzw);
  539.     lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  540.     lzw->next++;
  541.     lzw->prefix = code;
  542.     if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  543.         morebits(lzw);
  544. }
  545.  
  546. /* extract the next codeword from the input stream */
  547. static int32
  548. nextcode(up)
  549. struct usock *up;
  550. {
  551.     int32 code;
  552.     if(up->zin->code == -1) {    /* read the first character */
  553.         if((code = PULLCHAR(&up->ibuf)) == -1)
  554.             return -1;
  555.         up->zin->code = code >> up->zin->nextbit;
  556.     }
  557.     if(up->ibuf == NULLBUF)        /* next byte is not available yet */
  558.         return -1;
  559.     /* continue assembling the codeword */
  560.     up->zin->code |= ((int32) uchar(*up->ibuf->data) <<
  561.             (8 - up->zin->nextbit)) & (((int32) 1 <<
  562.             up->zin->codebits) - 1);
  563.     if(16 - up->zin->nextbit < up->zin->codebits) {
  564.         (void) PULLCHAR(&up->ibuf);
  565.         up->zin->nextbit -= 8; /* pull bits from a third byte */
  566.         return nextcode(up);
  567.     }
  568.     code = up->zin->code;
  569.     up->zin->code = -1;
  570.     up->zin->nextbit = (up->zin->nextbit + up->zin->codebits) % 8;
  571.     if(up->zin->nextbit == 0)
  572.         (void) PULLCHAR(&up->ibuf);
  573.     if(code == ZCC) {
  574.         cleartbl(up->zin);
  575.         return nextcode(up);
  576.     }
  577.     if(code == ZFLUSH) {
  578.         up->zin->prefix = -1;
  579.         return nextcode(up);
  580.     }
  581.     return code;
  582. }
  583. #endif
  584.